package com.二叉树2;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Given preorder and inorder traversal of a tree, construct the binary tree.
 *
 * Note:
 * You may assume that duplicates do not exist in the tree.
 *
 * For example, given
 *
 * preorder = [3,9,20,15,7]
 * inorder = [9,3,15,20,7]
 * Return the following binary tree:
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *    https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/943/
 */
public class 前序与中序构造二叉树 {
    static class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder.length == 0){
                return null;
            }
            Map<Integer,Integer> map = new HashMap<>();
            for(int i = 0 ;i<inorder.length;i++){
                map.put(inorder[i],i);
            }
            TreeNode root = new TreeNode(preorder[0]);
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            for(int i  = 1;i<preorder.length;i++){
                TreeNode tmp = stack.peek();
                int val = preorder[i];
                TreeNode node = new TreeNode(val);
                //左边
                if(map.get(val) < map.get(tmp.val)){
                    tmp.left = node;
                }
                //右边
                else{
                    TreeNode tmp2 = null;
                    while (!stack.isEmpty() && map.get(val) > map.get(stack.peek().val)){
                       tmp2 =  stack.pop();
                    }
                    tmp2.right = node;
                }
                stack.push(node);
            }
            return root;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            TreeNode treeNode = solution.buildTree(new int[]{1, 2, 3}, new int[]{2, 1, 3});

        }
    }
}
